public class KMP_1 {
    /**
     *KMP算法核心是利用匹配失败的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
     * KMP与BF的区别：kmp的主串i并不会回退，子串的j也不会移动到0号位置。
     * 找next的关键是从下标0开始找到离当前j前一个最近的一个子串，看是否有匹配成功的子串，若有则返回子串长度，若无则返回0
     * @param str 主串
     * @param sub 子串
     * @param pos 从子串的pos位置开始匹配
     * @return 子串在主串中的下标
     */

    public static int KMP(String str,String sub,int pos){
        if (str == null || sub == null)return  -1;//主串或子串为空时返回-1
        int lenStr=str.length();
        int lenSub=sub.length();
        if (lenStr == 0 || lenSub== 0)return  -1;//这段好像可以删了？
        if (pos < 0 || pos >=lenStr)return  -1;//匹配位置不合法
        int i=pos;//遍历主串
        int j=0;//遍历子串
        int[] next=new int [lenSub];
        getNext(sub,next);
        while (i < lenStr && j < lenSub){
            //j==-1 说明一开始就匹配失败了
            if (j==-1||str.charAt(i)==sub.charAt(j)){
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if(j>=lenSub) {
            return i-j;
        }else{
            return -1;
        }




    }
    public static void getNext(String sub, int[] next){
        next[0]=-1;
        next[1]=0;
        int i=2;//提前走了一步
        int k=0;//前一项的k
        for (; i < sub.length(); i++) {
            //遍历子串
            //p[i-1]==p[k]
            if( k==-1 || sub.charAt(i-1)==sub.charAt(k)){
                next[i]=k+1;
                k++;
                i++;
            }else{
                k=next[k];
            }

        }
    }
    public static void main(String[] args) {
        System.out.println(KMP("ababcabcdabcde","abcd",0));//5
        int k=KMP("ababcabcdabcde","abcdf",0);
        System.out.println(KMP("ababcabcdabcde","abcdf",0));//-1
        System.out.println(KMP("ababcabcdabcde","ab",0));//0

    }
}
